- лемма о накачке
- Programming: pumping lemma
Универсальный русско-английский словарь. Академик.ру. 2011.
лемма о накачке
Смотреть что такое "лемма о накачке" в других словарях:
Лемма о накачке — Лемма о накачке, или лемма о разрастании (англ. pumping lemma) в теории автоматов важная лемма, позволяющая во многих случаях проверить, является ли данный язык автоматным. Поскольку все конечные языки являются автоматными, эту проверку имеет… … Википедия
Лемма о накачке для регулярных языков — В теории формальных языков, лемма о накачке для регулярных языков описывает существенное свойство всех регулярных языков. Неформально она утверждает, что все достаточно длинные слова регулярного языка можно накачать, то есть повторить внутреннюю… … Википедия
Лемма о разрастании — Лемма о накачке, или лемма о разрастании (англ. pumping lemma) в теории автоматов важная лемма, позволяющая во многих случаях проверить, является ли данный язык автоматным. Поскольку все конечные языки являются автоматными, эту проверку… … Википедия
Лемма о разрастании для контекстно-свободных языков — Лемма о разрастании для контексто свободных языков лемма, по аналогии с одноименной леммой для регулярных языков позволяющая относительно несложно доказывать, что данный язык не является контекстно свободным. Содержание 1 Формулировка 2… … Википедия
Лемма Огдена — В теории формальных языков, лемма Огдена предоставляет расширение гибкости леммы о разрастании для контекстно свободных языков. Лемма Огдена утверждает, что если язык L контекстно свободен, то существует некоторое число p > 0 (где p может быть … Википедия
Теория автоматов — Теория автоматов раздел дискретной математики, изучающий абстрактные автоматы вычислительные машины, представленные в виде математических моделей и задачи, которые они могут решать. Теория автоматов наиболее тесно связана с… … Википедия
